home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0042_Quick Sort using LINK.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-11-02  |  2.5 KB  |  79 lines
  1. {
  2. IAN LIN
  3.  
  4. My pride and joy, this baby sorts FAST! This is For anyone who wants an
  5. example of code For sorting linked lists.
  6. }
  7.  
  8. {$A+,B-,D+,E-,F-,G+,I-,L+,N-,O-,R-,S+,V-,X-}
  9. {$M 4096,0,655360}
  10.  
  11. Procedure Theend; {could you think of a better name???}
  12. begin
  13.   Writeln('Assassin Technologies, NetRunner.');
  14.   {members: Ian Lin, Martin Young, William Parslow, Scott Rogers; just a new
  15.    Programming group, that's all.}
  16.   halt; {duh, kinda obvious you need to end the Program. :) }
  17. end;
  18.  
  19. Type
  20.   prec  = ^rec;
  21.   dType = String[96]; {put what you want here, it's fast anyhow}
  22.   rec   = Record
  23.     d : dType;
  24.     n : prec;       {"next" field"}
  25.  end;
  26.  
  27. Var
  28.   max, c : Word;    {maximum # of elements; Counter}
  29.   list,
  30.   list2,
  31.   node,
  32.   node2  : prec;    {first and second lists, temporary Pointers to nodes in the lists}
  33.   ram    : Pointer; {save heap state For use With mark/release}
  34.  
  35. begin
  36.   max := memavail div sizeof(dType); {this takes too long but is THE maximum}
  37.   max := 675;          {I picked this at random--it sorts in 2 seconds or so}
  38.   Exitproc := @Theend; {just to be fancy}
  39.   randomize;
  40.   mark(ram);
  41.   new(list);           {create list}
  42.   list^.d := Char(random(10) + 48); {put something in it}
  43.   node := list;
  44.   For c := 2 to max do
  45.   begin
  46.     new(node^.n);
  47.     node := node^.n;
  48.     node^.n := nil;
  49.     node^.d := Char(random(10) + 48);
  50.   end;
  51.  
  52.   new(list2);         {begin NEW sorted list}
  53.   list2^.n := list;   {steal the first node of list For list2}
  54.   list := list^.n;
  55.   list2^.n^.n := nil;
  56.   While list <> nil do
  57.   begin               {now steal 'em all and add them in order}
  58.     node  := list;    {point node to first node in LIST}
  59.     list  := list^.n; {advance LIST Pointer one node, first node is now seperate}
  60.     node2 := list2;   {ready to use NODE2 to find the correct entry point}
  61.     While (node2^.n <> nil) and (node^.d > node2^.n^.d) do
  62.       node2 := node2^.n; {advance NODE2 as needed Until it marks the
  63.                           right place For NODE to be inserted}
  64.     node^.n  := node2^.n;{insert NODE into the new list, in the correct order}
  65.     node2^.n := node;    {connect node to the previous nodes in new list, if any}
  66.   end;
  67.   list := list2^.n;      {point LIST back to the top of the list, now in order}
  68.  
  69.   node := list;          {the rest is just to display it}
  70.   Write('List: ');
  71.   While node <> nil do
  72.   begin                  {as usual (at least With me), NIL is the end}
  73.     Write(node^.d);
  74.     node := node^.n;
  75.   end;
  76.   Writeln;
  77.   release(ram);          {give all heap RAM back}
  78. end.
  79.